Modern database management systems (DBMS) process ever-increasing amounts of data. These database systems can store millions of data records. When accessing large databases, it is important to minimize the amount of time the database access takes, to ensure efficient and speedy operation of the database management system. Most large-scale database management systems use some form of optimization scheme, to ensure that operations executed on the DBMS, such as database queries, are executed as efficiently as possible.
In a database management system, optimization is the process of choosing an efficient way to execute a database query or manipulation action. Examples of such query or manipulation actions include searching, retrieving, modifying, organizing, adding, and/or deleting information from the database. These database query/manipulation actions are normally initiated by submitting commands to a database server in a database query language. One popular database query language is known as the Structured Query Language (“SQL”). For the purposes of explanation only, and not by way of limitation, the following description is made with particular reference to database statements involving SQL.
To execute a database query language statement (e.g., a SQL statement), the database system may have to perform various database operations involving the retrieval or manipulation of data from various database structures, such as tables and indexes. Examples of database operations include table scans, index lookups, data sorting, data grouping and/or aggregation, etc. Often, there exists many alternate ways to execute the SQL statement. For example, a single SQL statement can be executed in different ways by varying the order in which tables and indexes are accessed to execute the statement. The exact combination and order of database operations taken to execute the SQL statement can drastically change the efficiency or speed of execution for the statement. The combination and order of database operations that are used to execute a SQL statement is referred to as an “execution plan.”
As an example, consider the following SQL statement, which queries for the name of all employees having a salary equal to 100 from a database table “emp_table”:
SELECT employee_name
FROM emp_table
WHERE salary=100
A first execution plan could include a database operation that performs a full table scan of emp_table to execute the query. This first execution plan would retrieve every row from emp_table to identify particular rows that match the WHERE clause. Alternatively, if an index exists for the “salary” column of emp_table, then a second execution plan could involve a first database operation that accesses the index to identify rows that match the WHERE clause, and a second database operation that retrieves only those identified rows from the table. The index is considered an alternate access path to the data sought by the SQL statement.
Each execution plan has a “cost” that is associated with its execution. The cost of an execution plan can be expressed in terms of the resources that are consumed to execute the SQL statement using that execution plan. For example, the cost of an execution plan can be expressed in units of I/O usage, CPU usage, network usage, or memory usage.
An “optimizer” is used by a database system to choose what is believed to be the most efficient execution plan for a SQL statement. A “cost-based” optimizer bases its decision upon the costs of each execution plan. The cost-based optimizer typically generates a set of potential execution plans for the SQL statement based upon available access paths for the data sought to be operated upon by that statement. The cost is then estimated for each execution plan based upon, for example, data distribution and storage characteristics for database structures holding relevant data for the SQL statement. The optimizer then compares relative costs of the execution plans to choose the one with the smallest cost. This is typically done by adding up the total cost for each plan, and choosing the plan with the smallest sum.
One form of cost-based optimization is response time optimization. This form of optimization seeks to optimize a query to produce a result set in a minimum or near minimum amount of time. The optimizer selects the execution plan that is estimated to produce the desired result set in the minimal amount of time. There are various modes of response time optimization, including “all rows” and “first rows” modes. In all rows optimization mode, a query is optimized so that the estimated time to produce the full results set is minimized. In first rows optimization mode, a query is optimized so that the estimated time to produce an initial subset of the full results set is minimized, even if this causes the estimated time to produce the full results set to no longer be a minimum. All rows optimization mode is used where it is more important to return the entire results set quickly, for example, to generate reports and batch job query results sets. First rows optimization mode is used where it is more important to display an initial subset of the query results set, for example, to generate results sets for web-based or form-based online queries.
When optimizing a query according to a first rows optimization mode, conventional optimizers encounter difficulties in optimizing some classes of database operations. There are classes of database operations that have input parameters which are inconsistent with the first rows optimization mode. For example, there is a class of database operations, known as “blocking operations,” which consume all of their input data before producing any output data. Sort operations, for example, consume the entire data set to be sorted, sort the data, and only then start producing sorted output data. These blocking operations impose a “wait” condition on the execution of a query, while they load their input data. This wait condition is inconsistent with the first rows optimization mode, since it prevents the optimizer from delivering any rows of output before all rows of input have been consumed. Because of this wait condition, blocking operations are frequently, but not always, non-optimal when optimizing according to a first rows optimization mode. When doing first rows optimization, therefore, conventional optimizers eliminate blocking operations in the execution plans, by replacing them with equivalent non-blocking operations.
In some situations, however, the equivalent non-blocking operation has a higher execution cost than the blocking operation. Thus the conventional optimizer actually generates a sub-optimal execution plan by eliminating the blocking operation. This occurs because conventional optimizers do not take the relative costs of using the blocking and non-blocking operations into account when making a decision to replace one with the other. Conventional optimizers merely apply a fixed rule that replaces blocking operations with equivalent non-blocking operations. Therefore, systems and methods are needed to optimize queries containing blocking operations and other similar classes of database operations according to a cost-based optimization scheme.